package com.yangli.leecode.a;

/**
 * @author ly
 * @description #https://leetcode-cn.com/problems/regular-expression-matching/
 * <p>
 * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * <p>
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 * @data 2022/4/24
 */
public class IsMatch {
    public static void main(String[] args) {
        IsMatch isMatch = new IsMatch();
        System.out.println(isMatch.isMatch("aaaaabbbb", ".a*b*"));
    }

    //dp[i][j] 表示s的前i字符串能否被p的前j个匹配

    /**
     * 如果 p.charAt(j) == s.charAt(i) : dp[i][j] = dp[i-1][j-1]；
     * 如果 p.charAt(j) == '.' : dp[i][j] = dp[i-1][j-1]；
     * 如果 p.charAt(j) == '*'：
     * 如果 p.charAt(j-1) != s.charAt(i) : dp[i][j] = dp[i][j-2] //in this case, a* only counts as empty
     * 如果 p.charAt(j-1) == s.charAt(i) or p.charAt(j-1) == '.'：
     * dp[i][j] = dp[i-1][j] //in this case, a* counts as multiple a
     * or dp[i][j] = dp[i][j-1] // in this case, a* counts as single a
     * or dp[i][j] = dp[i][j-2] // in this case, a* counts as empty
     */

    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        // 这里dp矩阵是要大一圈的，用来处理s或者p为空串的情况，矩阵的行标i对应s的i-1，矩阵的列标j对应p的j-1
        boolean[][] f = new boolean[m + 1][n + 1]; //表示s的前i字符串能否被p的前j个匹配
        f[0][0] = true;
        //初始化
        for(int i = 1; i <= m; i++){
            f[i][0] = false;
        }
        // 初始化首行
        for(int j = 1; j <= n; j++){
            if(j == 1 || p.charAt(j - 1) != '*'){
                f[0][j] = false;
            } else {
                f[0][j] = f[0][j - 2];
            }
        }
        //j表示第几个字符 j= 0 表示空串 j=1 表示第一个字符 charAt需要减一
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j) == '.') {
                    f[i][j] = f[i - 1][j - 1];
                } else if (p.charAt(j) == '*') {
                    if (p.charAt(j - 1) != s.charAt(i)) {
                        f[i][j] = f[i][j - 2];
                    } else {
                        f[i][j] = f[i][j - 1] || f[i][j - 2] || f[i - 1][j];
                    }
                } else if (s.charAt(i) == p.charAt(j)) {
                    f[i][j] = f[i - 1][j - 1];
                }
            }
        }
        return f[m ][n];

    }
}
